package com.zjsru.oneday202208;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: likew
 * @Date: 2022/9/11
 * 雇佣 K 名工人的最低成本
 *
 * quality = [10,20,5], wage = [70,50,30], k = 2
 *
 * 3个工人完成1质量所需要的工资分别为7，2.5, 6
 *
 * 按题意需要选出2人为一组， 假设选择的是0号和1号
 *
 * 根据题目要求我们需要把1号完成1质量的工资提升到7， 也就是和0号一样， 这样才能保证公平， 此时需要支付给1号的工资为 20*7 = 140， 因此该组需要的工资为 70 + 140 = 210
 *
 * 如果0号和2号一组，需要的工资为(10+5) * 7 = 105,
 *
 * 如果1号和2号一组，需要的工资为 (25+5) * 6 = 180
 *
 * 因此选择0号和2号，需要的工资最低为105
 *
 * 可以看出，k个人的工资为 k个人的质量总和 * k个人的wage/quality的最大值
 */
public class MincostToHireWorkers {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int len = quality.length;
        double[][] ds = new double[len][2];
        for (int i = 0; i < len; i++) {
            ds[i][0] = wage[i] * 1.0 / quality[i];
            ds[i][1] = i * 1.0;
        }
        Arrays.sort(ds, (a, b) -> Double.compare(a[0], b[0]));
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        double ans = 1e18;
        for (int i = 0, tot = 0; i < len; i++) {
            int cur = quality[(int) ds[i][1]];
            tot += cur;
            q.add(cur);
            if (q.size() > k) {
                tot -= q.poll();
            }
            if (q.size() == k) {
                ans = Math.min(ans, tot * ds[i][0]);
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        MincostToHireWorkers mincostToHireWorkers = new MincostToHireWorkers();
        int[] quality = new int[]{10,20,5};
        int[] wage = new int[]{70,50,30};
        int k = 2;
        System.out.println(mincostToHireWorkers.mincostToHireWorkers(quality, wage, k));
    }
}
